package com.cn.codebrush.数组.回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author Boolean
 * @Date 2022/7/12 17:52
 * @Version 1.0
 */
public class No216组合总和III {
    public static void main(String[] args) {
        System.out.println(combinationSum3(4,60));
    }

    static List<List<Integer>> reslist = new ArrayList();
    public static List<List<Integer>> combinationSum3(int k,int n) {
        combinationSum3Helper(k,n,new ArrayList(),0,1);
        return reslist;
    }

    public static void combinationSum3Helper(int k,int n,List list,int sum,int start) {
        if(sum == n && list.size() == k){
            reslist.add(new ArrayList(list));
            return;
        }

        if(sum > n || list.size() > k){
            return;
        }

        for(int i=start;i<10;i++){
            list.add(i);
            combinationSum3Helper(k,n,list,sum+i,i+1);
            list.remove(list.size()-1);
        }

    }
}
